package com.cn.algorithm.two.graph;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public abstract class Graph<V, E> {

    protected WeightManager<E> weightManager;

    public Graph() {}

    public Graph(WeightManager<E> weightManager) {
        this.weightManager = weightManager;
    }

    public interface WeightManager<E> {
        int compare(E w1, E w2);
        E add(E w1, E w2);
        E zero();
    }


    public abstract int edgeSize();

    public abstract void addEdge(V from, V to);

    public abstract void addEdge(V from, V to, E weight);

    public abstract void removeEdge(V from, V to);


    public abstract int vertexSize();

    public abstract void addVertex(V value);

    public abstract void removeVertex(V value);

    public abstract void breadthFirstSearch(V v);

    public abstract void depthFirstSearch(V v);

    public abstract List<V> topologicalSort();

    public abstract Set<EdgeInfo<V, E>> minimumSpanningTree();

    public abstract Map<V, PathInfo<V, E>> shortestPath(V begin);



    public static class PathInfo<V, E> {

        protected E weight;
        protected LinkedList<EdgeInfo<V, E>> edgeInfos = new LinkedList<>();

        public PathInfo() {
        }

        public PathInfo(E weight) {
            this.weight = weight;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        public LinkedList<EdgeInfo<V, E>> getEdgeInfos() {
            return edgeInfos;
        }

        public void setEdgeInfos(LinkedList<EdgeInfo<V, E>> edgeInfos) {
            this.edgeInfos = edgeInfos;
        }
    }

    protected static class EdgeInfo<V, E> {

        private E weight;

        private V from;

        private V to;

        public EdgeInfo(V from, V to, E weight) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        public V getFrom() {
            return from;
        }

        public void setFrom(V from) {
            this.from = from;
        }

        public V getTo() {
            return to;
        }

        public void setTo(V to) {
            this.to = to;
        }
    }


}
